// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem240.h"

using namespace std;
// @before-stub-for-debug-end


/*
 * @lc app=leetcode.cn id=240 lang=cpp
 *
 * [240] 搜索二维矩阵 II
 *
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/description/
 *
 * algorithms
 * Medium (50.46%)
 * Likes:    968
 * Dislikes: 0
 * Total Accepted:    252.7K
 * Total Submissions: 499.1K
 * Testcase Example:  '[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]\n' +
  '5'
 *
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix =
 * [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],
 * target = 5
 * 输出：true
 *
 *
 * 示例 2：
 *
 *
 * 输入：matrix =
 * [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],
 * target = 20
 * 输出：false
 *
 *
 *
 *
 * 提示：
 *
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= n, m <= 300
 * -10^9 <= matrix[i][j] <= 10^9
 * 每行的所有元素从左到右升序排列
 * 每列的所有元素从上到下升序排列
 * -10^9 <= target <= 10^9
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
/* class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int row = matrix.size();
        int column = matrix[0].size();
        int n = row <= column ? row : column;
        int boundary = -1;
        for (int i = 0; i < n; ++i)
        {
            if (target == matrix[i][i])
            {
                return true;
            }
            else if (target < matrix[i][i])
            {
                boundary = i;
                break;
            }
            else
            {
                boundary = -1;
            }
        }
        if (boundary == 0)
        {
            return false;
        }
        else if (boundary > 0)
        {
            for (int i = boundary; i < matrix[0].size(); ++i)
            {
                if (matrix[boundary - 1][i] == target)
                {
                    return true;
                }
            }
            for (int i = 0; i < boundary; ++i)
            {
                if (matrix[boundary][i] == target)
                {
                    return true;
                }
            }
            return false;
        }
        // boundary = -1
        else
        {
            if (row == column)
            {
                return false;
            }
            else if (row < column)
            {
                for (int i = n ; i < column; ++i)
                {
                    if (matrix[n-1][i] == target)
                    {
                        return true;
                    }
                }
                return false;
            }
            else
            {
                for (int i = n; i < row; ++i)
                {
                    if (matrix[i][n-1] == target)
                    {
                        return true;
                    }
                }
                return false;
            }
        }
    }
}; */
class Solution{
    public:
    bool searchMatrix(vector<vector<int>> &matrix,int target){
        int m=matrix.size();
        if(m==0){
            return false;
        }
        int n=matrix[0].size();
        int i=0,j=n-1;
        while(i<m&&j>=0){
            if(matrix[i][j]==target){
                return true;
            }else if(matrix[i][j]>target){
                --j;
            }else{
                ++i;
            }
        }
        return false;
    }
};
// @lc code=end
